package leetcode;

/**
 * Created with IntelliJ IDEA.
 * Description:贪心算法
 * User: Lenovo
 * Date: 2022-02-17
 * Time: 11:34
 */
/*动态规划（DP：Dynamic Programming）：最有解问题-》贪心算法
* 局限性：从局部最优求解全局最优，其实贪心算法并没有把所有的方案都求解一边，只是按照每步都最大，有可能错过最优解
* 求最优解问题：需要我们把所有的方案数全部求解出来，然后进行比较，求解最优值
* 本质：还是需要把所有的可能性方案枚举一遍，然后求解最优值
* 搜索：深度优先搜索（DFS）
* 特征：最有子结构，无后效性。
* */
public class Day_04_01 {
    public static void main(String[] args) {

    }
}
class Solution {
    static int[][] dirs={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}} ;
    public double knightProbability(int n, int k, int row, int column) {
        double[][][] dp=new double[k+1][n][n];
        for(int step=0;step<=k;step++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(step==0){
                        dp[step][i][j]=1;
                    }else{
                        for(int[] dir:dirs){
                            int ni=i+dir[0];
                            int nj=j+dir[1];
                            if(ni>=0&&ni<n&&nj>=0&&nj<n){
                                dp[step][i][j]+=dp[step-1][ni][nj]/8;
                            }

                        }
                    }
                }
            }
        }
        return dp[k][row][column];
    }
}